package com.esunny.fptree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/**
 * FpTree
 * 
 * @author jenvin 2012-7-26 下午10:36:08
 */
public class FreqPrefixTree {

    private TreeNode  root     = null;

    private FreqItems items    = null;
    private int       nodeSize = 0;

    public FreqPrefixTree(List<List<String>> records, FreqItems freqItems){
        if (records == null) throw new IllegalArgumentException("records");
        if (freqItems == null) throw new IllegalArgumentException("freqItems");
        if (records.size() == 0) return;

        this.items = freqItems;
        // build prefix tree
        TreeNode rootNode = new TreeNode(); // 创建树的根节点
        for (List<String> rows : records) {
            LinkedList<String> orderRows = sortByFreqItems(rows, items);// 按 freqItem 排序
            TreeNode subTreeRoot = rootNode;
            TreeNode tmpRoot = null;
            if (rootNode.getChilds() != null) {
                while (!orderRows.isEmpty() && (tmpRoot = subTreeRoot.findChild(orderRows.peek())) != null) {
                    tmpRoot.countIncrement(1);
                    subTreeRoot = tmpRoot;
                    orderRows.poll();
                }
            }
            addNodes(subTreeRoot, orderRows);
        }
        this.root = rootNode;
    }

    /**
     * 3.2 把若干个节点作为指定指定节点的后代插入树中
     * 
     * @param ancestor
     * @param record
     * @param F1
     */
    public void addNodes(TreeNode ancestor, LinkedList<String> record) {
        if (record.size() <= 0) return;
        while (record.size() > 0) {
            String r = record.poll();
            TreeNode leafnode = new TreeNode(r);
            leafnode.setCount(1);
            leafnode.setParent(ancestor);
            ancestor.addChild(leafnode);
            nodeSize++;
            for (Item it : items) {
                if (it.getName().equals(r)) {
                    TreeNode links = it.getLinkNode();
                    if (links == null) {
                        it.setLinkNode(leafnode);
                    } else {
                        while (links.getNextLink() != null) {
                            links = links.getNextLink();
                        }
                        links.setNextLink(leafnode);
                    }
                    break;
                }
            }

            addNodes(leafnode, record);
        }
    }

    /**
     * 3.1把事务数据库中的一条记录按照F1（频繁1项集）中的顺序排序
     * 
     * @param rowRecods
     * @param f1
     * @return
     */
    public LinkedList<String> sortByFreqItems(List<String> rowRecods, FreqItems f1) {
        Map<String, Integer> map = new HashMap<String, Integer>();
        for (String r : rowRecods) {
            // 由于F1已经是按降序排列的，
            for (int i = 0; i < f1.size(); i++) {
                Item fItem = f1.get(i);
                if (fItem.getName().equals(r)) {
                    map.put(r, i);
                }
            }
        }

        List<Entry<String, Integer>> al = new ArrayList<Entry<String, Integer>>(map.entrySet());
        Collections.sort(al, new Comparator<Map.Entry<String, Integer>>() {

            @Override
            public int compare(Entry<String, Integer> arg0, Entry<String, Integer> arg1) {
                // 降序排列
                return arg0.getValue() - arg1.getValue();
            }
        });
        LinkedList<String> rest = new LinkedList<String>();
        for (Entry<String, Integer> entry : al) {
            rest.add(entry.getKey());
        }
        return rest;
    }

    public TreeNode getRoot() {
        return root;
    }

    public int getNodeSize() {
        return nodeSize;
    }

    private void toString(StringBuilder sb, TreeNode node) {
        sb.append(node.toString());
        List<TreeNode> children = node.getChilds();
        if (children != null && children.size() > 0) {
            for (TreeNode child : children) {
                // sb.append(child.toString());
                toString(sb, child);
            }
        }
        return;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        toString(sb, this.root);
        return sb.toString();
    }

}
